package com.zy.sort;

import com.google.common.base.Joiner;
import com.google.common.collect.Lists;

import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @Author zhaoyi
 * @date 2020/4/3
 * 计数排序
 */
public class CountSort {

    public static void main(String[] args) {

        /**
         * 考生的分数等级
         */
        List<String> level = Lists.newArrayList("B", "E", "C", "A", "B", "C", "A", "D");

        //对应等级的人数,根据等级排序
        List<Map.Entry<String, Long>> levelCount = level.stream()
                .collect(Collectors.groupingBy(s -> s, Collectors.counting()))
                .entrySet().stream().sorted(Comparator.comparing(Map.Entry::getKey))
                .collect(Collectors.toList());

        //集合变为小于等于当前分数的人数的集合,最后转换回MAP方便查询
        Long init = 0L;
        for (Map.Entry<String, Long> entry : levelCount) {
            entry.setValue(entry.getValue() + init);
            init = entry.getValue();
        }
        Map<String, Long> levelLessCountMap = levelCount.stream().collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

        List<String> result = Lists.newArrayList(level);
        //依次去分数放正确位置
        for (String key : level) {
            Long aLong = levelLessCountMap.get(key);
            result.set(aLong.intValue() - 1, key);
            levelLessCountMap.put(key, aLong - 1);
        }

        System.out.println(Joiner.on(",").skipNulls().join(result));


    }


}
